|
The -ary heap or -heap is a priority queue data structure, a generalization of the binary heap in which the nodes have children instead of 2.〔〔〔 Thus, a binary heap is a 2-heap, and a ternary heap is a 3-heap. According to Tarjan〔 and Jensen et al.,〔.〕 -ary heaps were invented by Donald B. Johnson in 1975.〔.〕 This data structure allows decrease priority operations to be performed more quickly than binary heaps, at the expense of slower delete minimum operations. This tradeoff leads to better running times for algorithms such as Dijkstra's algorithm in which decrease priority operations are more common than delete min operations.〔〔 Additionally, -ary heaps have better memory cache behavior than a binary heap, allowing them to run more quickly in practice despite having a theoretically larger worst-case running time.〔〔 Like binary heaps, -ary heaps are an in-place data structure that uses no additional storage beyond that needed to store the array of items in the heap.〔〔.〕 ==Data structure== The -ary heap consists of an array of items, each of which has a priority associated with it. These items may be viewed as the nodes in a complete -ary tree, listed in breadth first traversal order: the item at position 0 of the array forms the root of the tree, the items at positions 1– are its children, the next items are its grandchildren, etc. Thus, the parent of the item at position (for any ) is the item at position and its children are the items at positions through . According to the heap property, in a min-heap, each item has a priority that is at least as large as its parent; in a max-heap, each item has a priority that is no larger than its parent.〔.〕〔 The minimum priority item in a min-heap (or the maximum priority item in a max-heap) may always be found at position 0 of the array. To remove this item from the priority queue, the last item ''x'' in the array is moved into its place, and the length of the array is decreased by one. Then, while item ''x'' and its children do not satisfy the heap property, item ''x'' is swapped with one of its children (the one with the smallest priority in a min-heap, or the one with the largest priority in a max-heap), moving it downward in the tree and later in the array, until eventually the heap property is satisfied. The same downward swapping procedure may be used to increase the priority of an item in a min-heap, or to decrease the priority of an item in a max-heap.〔〔 To insert a new item into the heap, the item is appended to the end of the array, and then while the heap property is violated it is swapped with its parent, moving it upward in the tree and earlier in the array, until eventually the heap property is satisfied. The same upward-swapping procedure may be used to decrease the priority of an item in a min-heap, or to increase the priority of an item in a max-heap.〔〔 To create a new heap from an array of items, one may loop over the items in reverse order, starting from the item at position and ending at the item at position 0, applying the downward-swapping procedure for each item.〔〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「D-ary heap」の詳細全文を読む スポンサード リンク
|